package com.chj.chuji.tijie06;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class InorderTraversal {
	public static class TreeNode {
		int val = 0;
		TreeNode left = null;
		TreeNode right = null;

		public TreeNode(int val) {
			this.val = val;
		}
	}

	public static ArrayList<Integer> inorderTraversal(TreeNode root) {
		// write code here
		List<Integer> res = new ArrayList<Integer>();
		if (root != null) {
			Stack<TreeNode> stack = new Stack<TreeNode>();
			while (!stack.isEmpty() || root != null) {
				if (root != null) {
					stack.push(root);
					root = root.left;
				} else {
					root = stack.pop();
					res.add(root.val);
					root = root.right;
				}

			}
		}
		return (ArrayList<Integer>) res;
	}

	public static ArrayList<Integer> inorderTraversal1(TreeNode root) {
		// write code here
		List<Integer> res = new ArrayList<Integer>();
		dfs(root, res);
		return (ArrayList<Integer>) res;

	}

	private static void dfs(TreeNode root, List<Integer> res) {
		if (root == null)
			return;
		if (root.left != null)
			dfs(root.left, res);
		res.add(root.val);
		if (root.right != null)
			dfs(root.right, res);
	}

	public static void main(String[] args) {
		TreeNode head1 = new TreeNode(1);
		head1.right = new TreeNode(2);
		head1.right.left = new TreeNode(3);
		ArrayList<Integer> res = inorderTraversal(head1);
		for (int i = 0; i < res.size(); i++) {
			System.out.print(res.get(i) + ", ");
		}
		System.out.println();

		TreeNode head2 = new TreeNode(1);
		head2.right = new TreeNode(2);
		head2.right.left = new TreeNode(3);
		ArrayList<Integer> res2 = inorderTraversal1(head2);
		for (int i = 0; i < res2.size(); i++) {
			System.out.print(res2.get(i) + ", ");
		}
		System.out.println();
	}
}
